package 第三周;

/*
 * @author  YxinMiracle
 * @date  2022-04-27 17:36
 * @Gitee: https://gitee.com/yxinmiracle
 */

public class 从前序与中序遍历序列构造二叉树 {
    int[] preorder;
    int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return build(0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int p1, int p2, int i1, int i2) {
        if (p1>p2 || i1 > i2) return null;

        TreeNode treeNode = new TreeNode(preorder[p1]);
        int min = i1;
        while (inorder[min] != treeNode.val) min++;
        treeNode.left = build(p1+1,p1+(min-i1),i1,i1+min-1);
        treeNode.right = build(p1+(min-i1)+1,p2,min+1,i2);
        return treeNode;

    }


}
